interface NodeInterface {
  key: number;
  left: NodeInterface | null;
  right: NodeInterface | null;
}

class Node {
  public key: any;
  public left: any;
  public right: any;
  constructor(key: any) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

class SearchTree {
  private root: NodeInterface | null;
  constructor() {
    this.root = null;
  }

  preOverTreaverse() {

    this.preOrderTranverseNode(this.root)
  }

  // 先序遍历
  preOrderTranverseNode(node: NodeInterface | null) {
    if (node === null) return
    console.log(node.key)
    this.preOrderTranverseNode(node.left)
    this.preOrderTranverseNode(node.right)
  }

  // 中序遍历
  inOrderTranverse() {
    this.inOrderTranverseNode(this.root)
  }

  // 中序遍历
  inOrderTranverseNode(node: NodeInterface | null) {
    if (node === null) return
    this.inOrderTranverseNode(node.left)
    
    console.log(node.key)
    this.inOrderTranverseNode(node.right)
  }

  // 后序遍历
  houOrderTranverse() {
    this.houOrderTranverseNode(this.root)
  }

  // 后序遍历
  houOrderTranverseNode(node: NodeInterface | null) {
    if (node === null) return
    this.houOrderTranverseNode(node.left)
    this.houOrderTranverseNode(node.right)
    console.log(node.key)

  }

  // 插入
  insertNode(node: NodeInterface, newNode: NodeInterface) {
    if (newNode.key > node.key) {
      if (node.right === null) {
        node.right = newNode
      } else {
        this.insertNode(node.right, newNode)
      }
    }
    else {
      if (node.left === null) {
        node.left = newNode
      } else {
        this.insertNode(node.left, newNode)
      }

    }

  }

  insert(key: number) {
    var newNode = new Node(key);
    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }
  }

  min(): number | null {
    let node = this.root
    while (node?.left) {
      node = node.left
    }
    return node === null ? null : node.key
  }

  max(): number | null {
    let node = this.root
    while (node?.right) {
      node = node.right
    }
    return node === null ? null : node.key
  }

  search(key: number): boolean {
    return this.searchNode(this.root, key)
  }


  searchNode(node: NodeInterface | null, key: number): boolean {
    if (node === null) {
      return false
    }
    if (key > node.key) {
      return this.searchNode(node.right, key)
    }
    else if (key < node.key) {
      return this.searchNode(node.left, key)
    }
    else {
      return true
    }
  }

  remove(key: number) {
    if (this.root === null) return
    let cur = this.root
    let parent = null
    let isLeft = true
    while (cur.key !== key) {
      parent = cur
      if (key < cur.key) {
        if (cur.left !== null) {
          cur = cur.left
          isLeft = true
        }

      }
      else if (key > cur.key) {
        if (cur.right !== null) {
          cur = cur.right
          isLeft = false
        }
      }

    }
    
    // 当前的节点为叶子节点时
    if (cur.left === null && cur.right === null) {
      if (parent === this.root) {
        this.root = null
      }
      else if (parent && isLeft) {
        parent.left = null
      }
      else if (parent) {
        parent.right = null
      }
    }
    // 非度为2的二叉树 左有节点
    else if (cur.right === null) {
      if (this.root === cur) {
        this.root = cur.left
      }
      else if (isLeft && parent) {
        parent.left = cur.left
      }
      else if (parent) {
        parent.right = cur.left
      }
    }
    else if (cur.left === null) {
      if (this.root === cur) {
        this.root = cur.right
      }
      else if (isLeft && parent) {
        parent.left = cur.right
      }
      else if (parent) {
        parent.right = cur.right
      }
    }
    // 完全二叉树
    else {

    }
  }



}
export { SearchTree };
